Approximate Fraction Matching

Goal. We need to compare a fraction $\frac{a}{b} < t$ where $0 \leq a \leq b \leq 12\,800$ and $t\in[0,1]$. We want to approximate $t$ by a fraction $\hat{t} = \frac{c}{d \cdot p}$ where $p = 65\,519$ and $d \cdot p < 2^{32}$.

The approximation error is the maximum observable discrepancy.

$$ \max \vert \frac{a}{b} - \hat{t} \vert $$

Question. What are the optimal values of $c$ and $d$, such that

Without loss of generality we can assume $t \in F_n$, as we can always round $t$ up to the nearest value (and handle $t=1$ as a special case) without affecting the comparison.

Farey Sequences

Consider all distinct fractions in $[0,1]$ with denominators up to $n$. When ordered these form the Farey seqeunce of order $n$, the values of which are:

$$ F_n = \left\{ (a,b) \mid 0 ≤ a ≤ b ≤ n ∧ \gcd(a,b) = 1 \right\} $$

Some interesting results are known, for example

$$ \vert F_n \vert = 1 + \sum_{i\in[1,n]} φ(i) $$

where $φ$ is Euler's totient function. There is also a surprisingly simple algorithm to generate the sequence:

def farey_sequence(n, descending = False):
    a, b, c, d = (1, 1, n - 1, n) if descending else (0, 1, 1, n)
    yield (a, b)
    while 0 <= c <= n:
        k = (n + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
        yield (a, b)